Target devices such as field programmable gate arrays (FPGAs), structured application specific integrated circuits (ASICs), and ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The complexity of a large system often requires the use of electronic design automation (EDA) tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) compilation flow is hardware description language (HDL) compilation. HDL compilation involves performing synthesis, placement, routing, and timing analysis of the system on the target device.
Register retiming is a circuit optimization technique that is used to improve the performance of sequential circuits. Register retiming repositions registers (flip-flops) in the circuit without changing the combinational logic of the circuit. A theoretical formulation for performing global retiming was first introduced by Leiserson and Saxe. While their approach utilized algorithms that supported polynomial time complexity, it also required explicit computation of pair-wise delays between nodes on every path of the circuit as well as the identification of the minimum number of registers between those pairs of nodes. Subsequent attempts to perform global retiming included an approach by Shenoy and Rudell which eliminated redundant timing constraints in the retiming graph.